package com.ry.day1129;

import java.util.HashMap;
import java.util.Map;

//https://www.bilibili.com/video/BV1Eq4y1B7QL?spm_id_from=333.788.player.switch
public class LC32 {

    static class Solution {
        /**
         * @param source: A string
         * @param target: A string
         * @return: A string denote the minimum window, return "" if there is no such a string
         */
        public String minWindow(String source, String target) {
            //https://www.bilibili.com/video/BV1Eq4y1B7QL?spm_id_from=333.788.player.switch
            //双指针
           Map<Character,Integer> sm = new HashMap<>();
           Map<Character,Integer> tm = new HashMap<>();
            for (int i = 0; i < target.length(); i++) {
                char c = target.charAt(i);
                if(!tm.containsKey(c)){
                    tm.put(c,0);
                }

                tm.put(c,tm.get(c)+1);
            }

            String ans = "";
            int minwin = Integer.MAX_VALUE;
            int right =0;
            int matched =0;

            int n= source.length();
            for (int left = 0; left <n ; left++) {

                while (right<n && matched<tm.size()){
                    char ch = source.charAt(right);
                    if(!sm.containsKey(ch)){
                        sm.put(ch,0);
                    }
                    sm.put(ch,sm.get(ch)+1);
                    if(tm.containsKey(ch) && sm.get(ch).equals(tm.get(ch))){
                        matched++;
                    }
                    right++;
                }

                if(matched == tm.size()){
                    if(right-left < minwin){
                        minwin=right-left;
                        ans = source.substring(left,right);
                    }
                }
                char ch = source.charAt(left);
                sm.put(ch,sm.get(ch)-1);
                if(tm.containsKey(ch) && sm.get(ch).equals(tm.get(ch)-1)){
                    matched--;
                }
            }



            return ans;
        }
    }

    public static void main(String[] args) {
        Solution obj = new Solution();

        System.out.println(obj.minWindow("abc","ac"));
        System.out.println(obj.minWindow("adobecodebanc","abc"));
        System.out.println(obj.minWindow("abc","aa"));
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
32 · 最小子串覆盖
算法
中等
通过率
31%

题目
题解73
笔记
讨论99+
排名
记录
描述
给定两个字符串 source 和 target. 求 source 中最短的包含 target 中每一个字符的子串.

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


如果没有答案, 返回 "".
保证答案是唯一的.
target 可能包含重复的字符, 而你的答案需要包含至少相同数量的该字符.
0
<
=
l
e
n
(
s
o
u
r
c
e
)
<
=
100000
0<=len(source)<=100000
0
<
=
l
e
n
(
t
a
r
g
e
t
)
<
=
100000
0<=len(target)<=100000
样例
样例 1：

输入：

source = "abc"
target = "ac"
输出：

"abc"
解释：

"abc" 是 source 的包含 target 的每一个字符的最短的子串。

样例 2：

输入：

source = "adobecodebanc"
target = "abc"
输出：

"banc"
解释：

"banc" 是 source 的包含 target 的每一个字符的最短的子串。

样例 3：

输入：

source = "abc"
target = "aa"
输出：

""
解释：

没有子串包含两个 'a'。

挑战
O(n) 时间复杂度

相关知识
学习《2024年8月北美大厂最新面试真题精讲》课程中的1.6Amazon：最新面试精选003相关内容 ，了解更多相关知识！
标签
企业
C3 IoT
相关题目

857
最小的窗口子序列
困难

1169
字符串的排列
中等

1362
包含所有单词连接的子串
困难

1117
最小范围
困难

604
滑动窗口内数的和
简单
推荐课程

ACM金牌逐行带刷班
最适合懒人的刷题课--躺平看算法大神在线coding，讲解思路+现场debug，手撕面试高频题
1579/1588
已开启智能提示
发起考试
30 分 00 秒
12345678910

控制台
        历史提交

 */
